In large-scale information systems, objects stored in a database are usually assigned an identifier consisting, for example, in an alphanumeric string of characters. The identifier may be used as means for identifying a given object with a data structure of limited size. By processing the identifier instead of the object itself, resources of the overall systems are optimized. Objects processed and stored in databases may not be static in essence. Objects may be created, deleted and modified at various rates. Therefore, the identifiers may also be created, deleted and modified correspondingly.
However, for databases processing a large amount of data accessed by a large number of clients, creating, deleting, modifying and also assigning identifiers may become a task that impacts the overall performance of the system. One example of a performance parameter that can be impacted is the response time. Other examples are the memory needed for storing the identifiers and their association with the corresponding objects and the communication bandwidth for updating the identifiers and their correspondences.
In some applications, each object is assigned a unique identifier that represents the object in a unique fashion throughout the system. A field in which the use of unique identifiers in a database may be important is the management of travel reservations.
Travel companies such as airline companies and hotel companies for example use very sophisticated databases and reservation software for handling reservations by customers. A travel reservation involves a large number of participants: commercial agents, transportation companies, customs and other administrative bodies, etc. These participants are also usually distributed over large geographical regions. Therefore, a common database and communication architecture must be used to endure a proper management of the large amount of information that the travel specifications of each reservation by each customer represent. The common database is thus accessed by a large number of client devices (at the travel companies) simultaneously, and from a large number of locations.
TPF (acronym for “Transaction Processing Facility”) is an example of a real-time operating system developed by IBM™ for processing data transactions involved in travel reservation systems. Other systems exist, as would be understood by the person skilled in the art.
In order to share information concerning a given reservation, the travel industry has developed common descriptors and data structures to be used in the data transaction-processing systems. Historically, the airline industry defined the PNR (acronym for “Passenger Name Record”) which is a record in a database that contains information (including reservation information) concerning a traveller or a group of travellers travelling together. The purpose of the PNR was to make it possible for airline companies to exchange reservation information in case the travel involved several airlines for several destinations. IATA (acronym for “International Air Transportation Association”), the trade association regrouping the airline companies throughout the world, is the body that defines the standard for the PNR (content, format, etc.). Although PNRs had initially been defined for the airline industry, they are also used for hotel reservation, car rental, train bookings, etc.
In order to facilitate access to the PNRs, unique identifiers are associated with the PNRs. The unique identifiers are usually called “record locators” but other denominations exist. The record locators are typically defined as an alphanumeric string of characters, for example 6 characters (numbers and letters). The use of an alphanumeric string is the current standard in the industry.
The management of record locators must meet a large number of technical constraints. The following are exemplary constraints. One constraint is a high throughput, for example, more than 50 identifier requests per second. Another constraint is a low response delay, for example at least 90% of the identifier requests to be processed in less than a millisecond. Another constraint is being reliably uniquely associated with an active PNR at a given time and avoiding failure due to identification conflicts. Another constraint is being reusable once a previous use of the identifier is exhausted. Another constraint is guaranteeing the avoidance of “lost” identifiers, for example identifiers assigned to an inactive PNR without possibility to recover the identifier (e.g., for reuse). Another constraint is simplicity of operation and avoidance of manual interventions. Another constraint is respect of the communication constraints of the architecture of the system (messaging constraints and the like). Another constraint is being interoperable between transaction data processing systems (e.g., TPF developed by IBM™ and other systems). Another constraint is to respect standardization constraints.
To cope with such constraints, there is a need for an evolution from centralized mainframes to distributed systems wherein independent and redundant servers (called “backends”) can simultaneously and independently perform allocations of record locators for newly created reservation records. In some centralized mainframes, the record locators not only serve as identifiers for the PNRs but they also serve as a low-level address in the database. In order to generate the record locators, the centralized systems implement algorithms that can convert an address in the database into a record locator compliant with the standard. Such generation method for unique identifiers is not convenient for distributed architectures. The address-based generation cannot be implemented in each backend without an increase of the complexity of the system while keeping the constraints on the identifiers met (short size with a restricted number of characters, high performance, compatibility, etc.).
Thus, there is a need for improvements of unique identifier generation for database systems.